\input{euler.tex}

\begin{document}

\problem[358]{Cyclic Numbers}

A \emph{cyclic number} with $n$ digits has a very interesting property: When it is multiplied by $1, 2, 3, 4, \ldots, n$, all the products have exactly the same digits, in the same order, but rotated in a circular fashion.

The smallest cyclic number is the 6-digit number 142857. The next cyclic number is 0588235294117647 with 16 digits.

There is only one cyclic number for which, the eleven leftmost digits are 00000000137 and the five rightmost digits are 56789, with an unknown number of digits in the middle. Find the sum of all its digits.

\solution

The key to the solution is the following properties of a cyclic number:

1. A cyclic number of $(p-1)$ digits is the maximal recurring period of the decimal expansion of a prime $1/p$. Such primes are called \emph{full reptend primes}.

2. A cyclic number $n$ generated by $1/p$ has the property that $np = 999 \ldots 999$ ($p-1$ nines).

3. When split in half by its digits and added, the result is a sequence of 9's. For example, $142 + 857 = 999$.

With these properties, this problem is ready to solve. Let $n$ be the cyclic number to find, and $p$ be its generating prime. Since the last five digits of $n$ is 56789, we have
\[
56789 \times p \equiv 99999 \mod 100000 
\]
which gives $p \equiv 09891 \mod 100000$.

Next, note that $1.37 \times 10^{-9} < 1/p < 1.38 \times 10^{-9}$, which gives $724,637,681 < p \le 729,927,007$. Thus we just need to enumerate each prime $p$ ending with 09891 within this range, and test whether it is a full reptend prime.
 
The following result is useful in testing whether $p$ is full reptend prime: 

A prime is full reptend if and only if 10 is a primitive root modulo $p$, which means that the smallest solution to
\[
10^k \equiv 1 \mod p
\]
is $k = p - 1$. 

By Fermat's little theorem, $(p-1)$ is always a solution to the above equation. It is also easy to see that if $k$ is the smallest solution to the above equation, then $k$ must be a divisor of $(p-1)$. In addition, any exponent that is a multiple of $k$ satisfies the above equation. Therefore, if $k < p-1$, there must exist a prime factor $r$ of $(p-1)$ such that $k$ divides $(p-1)/r$. This allows us to test whether such $k$ exists by simply testing each prime factor of $p$.

Once we find such a prime, in order to sum the digits of its corresponding cyclic number, we can split the digits in the cyclic number in half and add them. It follows from Property 3 above that the sum of digits is equal to $9 \times (p-1) / 2$.

\answer

3284144505

\complexity

Let $m$ be the number of candidates in the range, and let $n$ be the largest candidate. Testing the primality of a candidate takes $\sqrt{n}$ trial divisions. There are no more than $m$ candidate primes. For each candidate prime, we need to test no more than $\log_2 n$ prime factors to check whether the prime is full reptend. Finally, testing whether a divisor $k$ satisfies $10^k \equiv 1$ takes no more than $\log_2 n$ modular exponential operations.

Time complexity: $\BigO(m \sqrt{n} + m (\log_2 n)^2)$

Space complexity: $\BigO(1)$

\reference

http://en.wikipedia.org/wiki/Cyclic\_number

http://mathworld.wolfram.com/CyclicNumber.html

http://mathworld.wolfram.com/FullReptendPrime.html

\end{document} 